/NOWRAPAROUND/LMAR=50/TMAR=50/RMAR=1700/BMAR=1/PMAR=0/XLINE=0/FONT#0=NGR13/USETI=000000015*TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX*

␈β↓N␈↓ ↓H␈ε"CS144b
␈βα	␈↓ ↓H␈ε"R.␈αW.␈αFlo␈α␈yd
␈ββ7␈↓ βz␈ε"En␈α␈tropy␈αof␈αSearching␈αand␈αSorting␈αProblems
␈β∧&␈↓ α⊂␈ε"If␈α
a␈α
system␈α
has␈α
equal␈α
lik␈α␈eliho␈α↓od␈α
of␈αbeing␈α
in␈ε(␈α
n␈ε"␈α
di{eren␈α␈t␈α
states,␈α
w␈α␈e␈α
sa␈α␈y␈αits␈ε@␈α
e␈α␈ntr␈α␈o␈α↓py
␈β∧Q␈↓ ↓H␈ε"is␈↓ ↓p␈ε"lg␈↓ α∩␈ε(n␈ε").␈α≤The␈α⊂expected␈α⊃time␈α⊂to␈α⊂determine␈α⊂which␈α⊂state␈α⊂the␈α⊃system␈α⊂is␈α⊂in,␈α⊃by␈α⊃tests
␈β∧⎇␈↓ ↓H␈ε"with␈α⊃t␈α␈w␈α␈o␈α⊃outcomes,␈α∪can␈α⊃not␈α∩be␈α⊃less␈α⊃than␈α∩the␈α⊃en␈α␈tropy.␈α A␈α⊃test␈α∩which␈α⊃is␈α⊃true␈α∩in
␈β¬(␈↓ ↓H␈ε(pn␈ε"␈α∞of␈α∂the␈α∞states␈α∂(0␈α∞<␈ε(␈α∂p␈ε"␈α∞<␈α∂1)␈α∞reduces␈α∂the␈α∂en␈α␈tropy,␈α∂on␈α∂the␈α∞a␈α␈v␈α␈erage,␈α∂from␈↓ 
c␈ε"lg␈↓ 
␈␈ε"(␈ε(n␈ε")␈α∂to
␈β¬S␈↓ ↓H␈ε(p␈↓ ↓`␈ε"lg␈↓ ↓|␈ε"(␈ε(pn␈ε"␈α␈)␈αβ+␈↓ αe␈ε(p␈↓ α⎇␈ε"lg␈↓ β→␈ε"(␈↓ β%␈ε(p␈↓ β7␈ε(n␈ε"),␈α
where␈↓ ∧R␈ε(p␈↓ ∧n␈ε"=␈α
1␈ε6␈αβ␈␈ε(␈αβp␈ε".␈α∂The␈α	change␈α
in␈α	en␈α␈tropy␈α	is␈ε6␈α
␈␈ε"(␈ε(p␈↓ 	R␈ε"lg␈↓ 	t␈ε(p␈ε"␈αβ+␈↓ 
0␈ε(p␈↓ 
H␈ε"lg␈↓ 
j␈ε(p␈↓ 
|␈ε")␈ε6␈α
∀␈ε"␈α
1,
␈β¬[␈↓ αe␈∧¬[αeα∩␈↓ β%␈∧¬[β%α∩␈↓ ∧R␈∧¬[∧Rα∩␈↓ 
0␈∧¬[
0α∩␈↓ 
j␈∧¬[
jα∩
␈β¬}␈↓ ↓H␈ε"with␈α∞equalit␈α␈y␈α∂only␈α∞when␈ε(␈α∂p␈ε"␈α∞=␈α∞1/2.␈α↔This␈α∂change␈α∞is␈α∂the␈ε@␈α∞info␈α↓rmatio␈α↓n␈ε"␈α∂gained␈α∞by␈α∂the
␈βε)␈↓ ↓H␈ε"test.
␈βεe␈↓ α⊂␈ε"The␈α	graph␈α	of␈α	information␈ε@vs.␈ε(␈α∂p␈ε"␈α	lo␈α↓oks␈α	a␈α	bit␈α	lik␈α␈e␈α
a␈α	parabola␈α	passing␈α	through␈α
(0,␈αε0),
␈βπ⊂␈↓ ↓H␈ε"(1/2,␈αε1)␈α
and␈α
(1,␈αε0);␈α
ho␈α␈w␈α␈ev␈α␈er,␈α∞it␈α
is␈α
v␈α␈ertical␈α
at␈α
0␈α
and␈α
1,␈α
and␈α
has␈α
a␈α
sligh␈α␈tly␈α
larger␈α∞area
␈βπ;␈↓ ↓H␈ε"than␈αthe␈αparabola␈α(1/(2␈↓ ∧B␈ε"ln␈↓ ∧f␈ε"2)␈αvs.␈α⊂2/3).
␈βm␈↓ 	(␈ε↓R
␈β|␈↓ 	@␈ε%1
␈βλ␈↓ α⊂␈ε"If␈αa␈α
test␈α
has␈α
a␈α
v␈α}ariable␈α
probabilit␈α␈y,␈α
with␈αdistribution␈↓ λ\␈ε(f␈↓ λr␈ε"(␈ε(p␈ε")(␈↓ 	V␈ε(f␈↓ 	l␈ε"(␈ε(p␈ε")␈ε(dp␈ε"␈α=␈α1),␈α∞the
␈β≥␈↓ 	9␈ε%0
␈β"␈↓ πM␈ε↓R
␈β1␈↓ πe␈ε%1
␈β=␈↓ ↓H␈ε"expected␈αinformation␈α
from␈α
the␈αtext␈α
is␈↓ ε)␈ε(I␈↓ ε;␈ε"(␈↓ εG␈ε(f␈↓ ε\␈ε")␈α=␈ε6␈α␈␈↓ π{␈ε(f␈↓ λ⊂␈ε"(␈ε(p␈ε")(␈ε(p␈↓ λ↑␈ε"lg␈↓ 	␈ε(p␈ε"␈α	+␈↓ 	G␈ε(p␈↓ 	←␈ε"lg␈↓ 
↓␈ε(p␈↓ 
∪␈ε")␈ε(d␈α↓p␈ε".␈α⊃O$en␈↓ F␈ε(f
␈βF␈↓ 	G␈∧F	Gα∩␈↓ 
↓␈∧F
↓α∩
␈βM␈↓ βK␈ε↓P␈↓ 	.␈ε↓P
␈βR␈↓ π↑␈ε%0
␈βb␈↓ ∧a␈ε+i
␈βh␈↓ ↓H␈ε"is␈α∂a␈α∞polynomial␈↓ ∧0␈ε(a␈↓ ∧O␈ε(p␈↓ ∧n␈ε";␈α⊂if␈α∂so,␈α∂the␈α∂expected␈α∂information␈α∂is␈↓ 
∪␈ε(a␈↓ 
2␈ε(b␈ε"(␈ε(i␈ε"␈α↓),␈α⊂where
␈βu␈↓ ∧C␈ε+i␈↓ 
&␈ε+i
␈βz␈↓ βq␈ε+i␈ε9∃␈↓ 	T␈ε+i␈ε9∃
␈β⎇␈↓ ∧~␈ε%0␈↓ 	|␈ε%0
␈β
λ␈↓ α]␈ε↓R
␈β
↔␈↓ αu␈ε%1
␈β
≥␈↓ β≡␈ε+i
␈β
#␈↓ ↓H␈ε(b␈ε"(␈ε(i␈ε")␈α
=␈ε6␈α
␈␈↓ β␈ε(p␈↓ β*␈ε"(␈ε(p␈↓ βN␈ε"lg␈↓ βp␈ε(p␈ε"␈αλ+␈↓ ∧6␈ε(p␈↓ ∧N␈ε"lg␈↓ ∧p␈ε(p␈↓ ¬α␈ε")␈ε(d␈α↓p␈ε".
␈β
+␈↓ ∧6␈∧
+∧6α∩␈↓ ∧p␈∧
+∧pα∩
␈β
8␈↓ αn␈ε%0
␈β
↑␈↓ α⊂␈ε"Since␈α⊃the␈α⊃second␈α∩part␈α⊃of␈α⊃this␈α⊃in␈α␈tegral␈α∩is␈α⊃messy␈α⊃for␈α∩large␈ε(␈α⊃i␈ε",␈α∪w␈α␈e␈α⊃simplify␈α∩the
␈β∞
␈↓ ↓H␈ε"problem␈αλusing␈α	the␈α	fact␈α	that␈↓ ∧v␈ε(I␈↓ ¬π␈ε"(␈↓ ¬∪␈ε(f␈↓ ¬)␈ε"(␈ε(p␈ε"))␈α
=␈↓ ε↔␈ε(I␈↓ ε(␈ε"(␈↓ ε4␈ε(f␈↓ εJ␈ε"(1␈ε6␈α↓␈␈ε(␈ααp␈ε"))␈α
=␈↓ πq␈ε(I␈↓ λα␈ε"(␈↓ λ∞␈ε(g␈↓ λ ␈ε"(␈ε(p␈ε")),␈α
where␈↓ 	O␈ε(g␈↓ 	`␈ε"(␈ε(p␈ε")␈α
=␈α
.5(␈↓ 
j␈ε(f␈↓ ␈ε"(␈ε(p␈ε"))␈αα+
␈β∞5␈↓ ↓H␈ε(f␈↓ ↓]␈ε"(1␈ε6␈α␈␈ε(␈αp␈ε")).␈α"F␈α⎇or␈α∩giv␈α␈en␈↓ ∧8␈ε(f␈↓ ∧M␈ε",␈↓ ∧k␈ε(g␈↓ ¬∂␈ε"is␈α∩a␈α∩distribution␈α∩yielding␈α∩the␈α∩same␈α∩information␈α∩and
␈β∞`␈↓ ↓H␈ε"symmetric␈αaround␈ε(␈αp␈ε"␈α
=␈α
.5␈α$.
␈β∂≤␈↓ α⊂␈ε"F␈α⎇rom␈αhere␈αon,␈αw␈α␈e␈αassume␈αthat␈↓ ¬x␈ε(f␈↓ ε
␈ε"(␈ε(p␈ε")␈αis␈αsymmetric␈αaround␈ε(␈αp␈ε"␈α
=␈α
1/2,␈αso
␈β∂↑␈↓ εI␈ε"1
␈β⊃C

␈β↓<␈↓ αi␈ε↓Z␈↓ εY␈ε↓Z␈↓ 	m␈ε↓Z
␈β↓E␈↓ β
␈ε%1␈↓ ε⎇␈ε%1␈↓ 
⊃␈ε%1
␈β↓P␈↓ 	?␈ε"2
␈β↓h␈↓ ↓H␈ε(I␈↓ ↓Y␈ε"(␈↓ ↓e␈ε(f␈↓ ↓{␈ε")␈α
=␈ε6␈α
␈␈↓ β#␈ε(f␈↓ β9␈ε"(␈ε(p␈ε")␈ε6↓␈ε"(␈ε(p␈↓ ∧⊃␈ε"lg␈↓ ∧3␈ε(p␈ε"+␈↓ ∧i␈ε(p␈↓ ¬↓␈ε"lg␈↓ ¬#␈ε(p␈ε")␈ε(dp␈ε"␈α
=␈ε6␈α
␈␈ε"2␈↓ π∪␈ε(f␈↓ π)␈ε"(␈ε(p␈ε")␈ε6↓␈ε(p␈↓ πu␈ε"lg␈↓ λ↔␈ε(pdp␈ε"␈α
=␈ε6␈α
␈␈↓ 
(␈ε(f␈↓ 
=␈ε"(␈ε(p␈ε")␈ε6↓␈ε(p␈↓ 	␈ε"ln␈↓ -␈ε(pdp␈ε".
␈β↓p␈↓ ∧i␈∧↓p∧iα∩
␈β↓|␈↓ 	-␈∧↓|	-α6
␈βα↓␈↓ 	-␈ε"ln␈↓ 	Q␈ε"2
␈βα∞␈↓ α⎇␈ε%0␈↓ εm␈ε%0␈↓ 
↓␈ε%0
␈βα>␈↓ ∧C␈ε↓P␈↓ πO␈ε↓P␈↓ λY␈ε↓R
␈βαM␈↓ λq␈ε%1
␈βαQ␈↓ D␈ε+a
␈βαS␈↓ ¬Y␈ε+i␈↓ 	~␈ε+i
␈βαV␈↓ 	$␈ε%+1
␈βαX␈↓ π&␈ε%2␈↓ 
}␈ε%2
␈βαY␈↓ ↓H␈ε"When␈↓ α,␈ε(f␈↓ αI␈ε"is␈αλa␈αλpolynomial,␈↓ ¬(␈ε(a␈↓ ¬G␈ε(p␈↓ ¬e␈ε",␈↓ ¬x␈ε(I␈↓ ε	␈ε"(␈↓ ε∃␈ε(f␈↓ ε+␈ε")␈α
=␈ε6␈α
␈␈↓ λ4␈ε(a␈↓ 	λ␈ε(p␈↓ 	Y␈ε"ln␈↓ 	⎇␈ε(pdp␈ε"␈α
=
␈βα[␈↓ T␈ε-i
␈βαf␈↓ ¬;␈ε+i␈↓ λG␈ε+i
␈βαk␈↓ ∧i␈ε+i␈ε9␈α␈∃␈↓ πu␈ε+i
␈βαm␈↓ p␈ε'2
␈βαn␈↓ ¬⊃␈ε%0␈↓ π↔␈∧αnπ↔α.␈↓ π␈␈ε%=0␈↓ λj␈ε%0␈↓ 
o␈∧αn
oα.␈↓ %␈∧αn%α[␈↓ /␈ε+i
␈βαo␈↓ π↔␈ε%ln␈↓ π6␈ε%2␈↓ 
o␈ε%ln␈↓ ∞␈ε%2
␈βαq␈↓ %␈ε%(␈↓ 9␈ε%+2␈↓ f␈ε%)
␈ββ
␈↓ ¬}␈ε%1␈↓ ε%␈ε%1
␈ββ∞␈↓ ↓H␈ε"Examples:␈α∀(1)␈↓ β8␈ε(f␈↓ βM␈ε"(␈ε(p␈ε")␈α⊃=␈α⊃1.␈↓ ∧v␈ε(I␈↓ ¬π␈ε"(␈↓ ¬∪␈ε(f␈↓ ¬)␈ε")␈α⊂=␈↓ εX␈ε"=␈α⊃.72␈↓ π;␈ε(l␈↓ πF␈ε"3␈α⊂(2)␈↓ λ#␈ε(f␈↓ λ8␈ε"(␈ε(p␈ε")␈α⊃=␈α⊃6␈ε(p␈ε"(1␈ε6␈α
␈␈ε(␈αp␈ε").␈↓ 
h␈ε(I␈↓ 
y␈ε"(␈↓ ¬␈ε(f␈↓ ≠␈ε")␈α⊃=
␈ββ"␈↓ ¬}␈∧β"¬}α∂␈↓ ε∃␈∧β"ε∃α.
␈ββ#␈↓ ¬}␈ε%2
␈ββ$␈↓ ε∃␈ε%ln␈↓ ε4␈ε%2
␈ββ6␈↓ λR␈ε%2␈↓ 	[␈ε%2
␈ββ8␈↓ α∂␈ε%2␈↓ αc␈ε%1␈↓ β6␈ε%1␈↓ ∧3␈ε%7␈↓ ¬β␈ε%1
␈ββ9␈↓ ↓H␈ε"6␈ε6␈α↓␈↓ α=␈ε6↓␈↓ αS␈ε"(␈↓ α}␈ε6␈␈↓ βP␈ε")␈↓ βp␈ε"=␈↓ ∧Z␈ε6↓␈↓ ¬9␈ε"=␈α∀.8416␈α∩(3)␈↓ π⊃␈ε(f␈↓ π&␈ε"(␈ε(p␈ε")␈α∀=␈α∀30␈↓ λ@␈ε(p␈↓ λc␈ε"(1␈ε6␈α␈␈ε(␈αp␈↓ 	O␈ε")␈↓ 	k␈ε".␈↓ 
↔␈ε(I␈↓ 
(␈ε"(␈↓ 
4␈ε(f␈↓ 
J␈ε")␈α∀=␈α∀30␈ε6␈α↓
␈ββN␈↓ α␈∧βNαα.␈↓ αc␈∧βNαcα∂␈↓ αc␈ε%9␈↓ β.␈∧βNβ.α≡␈↓ β.␈ε%16␈↓ ∧,␈∧βN∧,α≡␈↓ ∧,␈ε%12␈↓ ∧t␈∧βN∧tα.
␈ββO␈↓ α␈ε%ln␈↓ α≡␈ε%2␈↓ ∧t␈ε%ln␈↓ ¬∪␈ε%2
␈ββa␈↓ λ↑␈ε%3␈↓ 	g␈ε%3
␈ββc␈↓ ↓[␈ε%2␈↓ α∃␈ε%1␈↓ αo␈ε%2␈↓ βI␈ε%1␈↓ ∧B␈ε%37␈↓ ∧w␈ε%1
␈ββe␈↓ ↓⎇␈ε"(␈↓ α7␈ε6␈␈↓ β⊃␈ε"+␈↓ βc␈ε")␈↓ ∧∧␈ε"=␈↓ ¬.␈ε"=␈α∃.8897␈α∪(4)␈↓ π	␈ε(f␈↓ π≡␈ε"(␈ε(p␈ε")␈α∃=␈α∃140␈↓ λL␈ε(p␈↓ λo␈ε"(1␈ε6␈α␈␈ε(␈αp␈↓ 	[␈ε")␈↓ 	x␈ε".␈↓ 
α␈ε(I␈↓ 
∀␈ε"(␈↓ 
 ␈ε(f␈↓ 
5␈ε")␈α∃=␈α∃140␈ε6␈α
↓
␈ββy␈↓ ↓L␈∧βy↓Lα.␈↓ α
␈∧βyα
α≡␈↓ α
␈ε%16␈↓ αg␈∧βyαgα≡␈↓ αg␈ε%25␈↓ βA␈∧βyβAα≡␈↓ βA␈ε%36␈↓ ∧B␈∧βy∧Bα≡␈↓ ∧B␈ε%60␈↓ ∧h␈∧βy∧hα.
␈ββz␈↓ ↓L␈ε%ln␈↓ ↓j␈ε%2␈↓ ∧h␈ε%ln␈↓ ¬ε␈ε%2
␈β∧∞␈↓ ↓[␈ε%2␈↓ α∃␈ε%1␈↓ αo␈ε%3␈↓ βI␈ε%3␈↓ ∧#␈ε%1␈↓ ¬⊂␈ε%533␈↓ ¬s␈ε%1
␈β∧⊂␈↓ ↓⎇␈ε"(␈↓ α7␈ε6␈␈↓ β⊃␈ε"+␈↓ βk␈ε6␈␈↓ ∧=␈ε")␈↓ ∧Y␈ε"=␈↓ ¬K␈ε6↓␈↓ ε$␈ε"=␈α⊂.9154␈α∂Th␈α␈us␈α∂the␈α∂information␈α∂e}ciency␈α⊂of
␈β∧$␈↓ ↓L␈∧∧$↓Lα.␈↓ α
␈∧∧$α
α≡␈↓ α
␈ε%25␈↓ αg␈∧∧$αgα≡␈↓ αg␈ε%36␈↓ βA␈∧∧$βAα≡␈↓ βA␈ε%49␈↓ ∧≠␈∧∧$∧≠α≡␈↓ ∧≠␈ε%64␈↓ ¬⊂␈∧∧$¬⊂α-␈↓ ¬⊂␈ε%840␈↓ ¬c␈∧∧$¬cα.
␈β∧%␈↓ ↓L␈ε%ln␈↓ ↓j␈ε%2␈↓ ¬c␈ε%ln␈↓ εα␈ε%2
␈β∧;␈↓ ↓H␈ε"Quicksort␈αwith␈αsample␈αsizes␈α1,␈α3,␈α5,␈αand␈α7␈αis␈αrespectiv␈α␈ely␈α.72,␈α.84,␈α.89,␈αand␈α.92.
␈β∧f␈↓ α⊂␈ε"In␈αgeneral,␈αusing␈αa␈αsample␈αsize␈αof␈ε(␈αs␈ε"␈αresults␈αin␈αinformation␈αe}ciency
␈β¬7␈↓ βf␈ε↓∩␈↓ λP␈ε↓∪
␈β¬8␈↓ ∧⊗␈ε"1␈↓ ¬⊂␈ε"1␈↓ ε
␈ε"1␈↓ λβ␈ε"1␈↓ 	⊗␈ε"1
␈β¬P␈↓ ∧J␈ε"+␈↓ ¬D␈ε"+␈↓ ε>␈ε"+␈↓ εj␈ε6↓␈αε↓␈αε↓␈↓ π≤␈ε"+␈↓ λn␈ε6↓
␈β¬d␈↓ ∧␈∧¬d∧α>␈↓ ∧z␈∧¬d∧zα>␈↓ ¬t␈∧¬d¬tα>␈↓ πL␈∧¬dπLα↓␈↓ 	∧␈∧¬d	∧α6
␈β¬j␈↓ ∧␈ε"1␈ε6␈αλ↓␈ε"␈αλ2␈↓ ∧z␈ε"3␈ε6␈αλ↓␈ε"␈αλ4␈↓ ¬t␈ε"5␈ε6␈αλ↓␈ε"␈αλ6␈↓ πL␈ε(s␈ε"(␈ε(s␈ε"␈αλ+␈αλ1)␈↓ 	∧␈ε"ln␈↓ 	(␈ε"2
␈βε;␈↓ α⊂␈ε"If␈α∂a␈α⊂system␈α∂has␈α⊂probabilit␈α␈y␈↓ ¬S␈ε(q␈↓ ε␈ε"of␈α⊂being␈α∂in␈α⊂the␈ε(␈α⊂i␈ε"th␈α⊂of␈ε(␈α∂n␈ε"␈α⊂states,␈α⊂its␈α⊂en␈α␈tropy␈α⊂is
␈βεG␈↓ ¬d␈ε+i
␈βεK␈↓ ↓r␈ε↓P
␈βε[␈↓ α_␈ε+n
␈βεf␈↓ ↓H␈ε6␈␈↓ αW␈ε(q␈↓ α{␈ε"lg␈↓ β≥␈ε(q␈↓ β;␈ε".␈α∩The␈α
expected␈α
time␈α
to␈α
determine␈α
which␈α
state␈α
the␈α
system␈αis␈α
in,␈α∞by
␈βεr␈↓ αi␈ε+i␈↓ β/␈ε+i
␈βεx␈↓ α_␈ε+i
␈βε{␈↓ α"␈ε%=1
␈βπ⊃␈↓ ↓H␈ε"an␈α␈y␈αalgorithm,␈α
is␈α
no␈αless␈α
than␈α
the␈αen␈α␈tropy.␈α∩Example:␈α
W␈α⎇e␈α
are␈α
searching␈αa␈α
table␈α
for
␈βπ<␈↓ ↓H␈ε"a␈αparticular␈α
k␈α␈ey.␈α∩Its␈ε@␈α
a␈αp␈α↓r␈α␈io␈α↓ri␈ε"␈αdistribution␈α
is␈α
kno␈α␈wn␈α
to␈αbe␈α
normal,␈α
with␈α
v␈α}ariance␈α
V.
␈βπ\␈↓ ¬y␈ε'2
␈βπa␈↓ ¬P␈ε9␈␈↓ ¬n␈ε+i␈↓ ε/␈ε+V
␈βπd␈↓ επ␈ε%/(2␈↓ εG␈ε%)
␈βπg␈↓ ↓H␈ε"Its␈α∞distribution␈α∂is␈α∞then␈↓ ∧@␈ε(q␈↓ ∧l␈ε"=␈↓ ¬≡␈ε(K␈↓ ¬A␈ε(e␈↓ εS␈ε".␈α↔The␈α∂en␈α␈tropy␈α∞of␈α∂this␈α∞distribution␈α∂is␈α∂ap-
␈βπr␈↓ ¬p␈ε↓⊂␈↓ π~␈ε↓⊃
␈βπt␈↓ ∧Q␈ε+i
␈βλ␈↓ β]␈ε↓R␈↓ λr␈ε↓R
␈βλ␈↓ βu␈ε91␈↓ 	
␈ε91
␈βλ⊂␈↓ ∧n␈ε'1␈↓ ε?␈ε'2␈↓ 
'␈ε'2
␈βλ∃␈↓ ∧@␈ε9␈␈↓ ∧]␈ε+x␈↓ ¬$␈ε+V␈↓ ε⊃␈ε9␈␈↓ ε/␈ε+x␈↓ εv␈ε+V␈↓ 	y␈ε9␈␈↓ 
↔␈ε+x␈↓ 
T␈ε+V
␈βλ↔␈↓ λ-␈ε+K
␈βλ_␈↓ ∧|␈ε%/(2␈↓ ¬<␈ε%)␈↓ εN␈ε%/(2␈↓ π∞␈ε%)␈↓ 	Y␈ε%2␈↓ 
6␈ε%/2
␈βλ≠␈↓ ↓H␈ε"pro␈α␈ximately␈ε6␈α␈␈↓ β4␈ε(K␈↓ ∧0␈ε(e␈↓ ¬N␈ε"lg␈↓ εα␈ε(e␈↓ π,␈ε(dx␈ε"␈α
=␈↓ 	E␈ε(x␈↓ 	j␈ε(e␈↓ 
n␈ε(dx␈ε"␈α
=
␈βλ-␈↓ βn␈ε9␈␈α␈1␈↓ 	β␈ε9␈␈α␈1
␈βλ.␈↓ λ≥␈ε+V
␈βλ0␈↓ λ∞␈∧λ0λ∞αZ
␈βλ1␈↓ λ∞␈ε%2␈↓ λ:␈ε%ln␈↓ λY␈ε%2
␈β∂↑␈↓ εI␈ε"2
␈β⊃C/FONT#1=cmathx[XGP,SYS]=⊂⊃∩∪PRZZ/FONT#34=cmr10[XGP,SYS]=$()+,-./0123456789:;<=ACEFIOPQRSTVWabcdefghiklmnopqrstuvwxyz{}}/FONT#37=cmr7[XGP,SYS]=()+/0123456789=lnn/FONT#39=cmr5[XGP,SYS]=122/FONT#40=cmi10[XGP,SYS]=IKabdefgilnpqsxx/FONT#43=cmi7[XGP,SYS]=KVainxx/FONT#45=cmi5[XGP,SYS]=ii/FONT#54=cmsy10[XGP,SYS]=↓∀∀/FONT#57=cmsy7[XGP,SYS]=∃11/FONT#64=cmti10[XGP,SYS]=.aefimnoprstvyy